#include <assert.h>
#include <stddef.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>
typedef int QDataType;
typedef struct QListNode 
{ 
	struct QListNode* _next; 
	QDataType _data; 
}QNode; 
 
// 队列的结构 
typedef struct Queue 
{ 
	QNode* front; //队头
	QNode* rear;  //队尾
    int size;//计数
}Queue; 
// 初始化队列 
void QueueInit(Queue* q)
{
    q->front=NULL;
    q->rear=NULL;
    q->size=0;
}

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
    assert(q);
    QNode* newNode=(QNode*)malloc(sizeof(QNode));
    if(newNode==NULL)
    {
        perror("malloc fail:");
        exit(-1);
    }
    newNode->_data=data;
    newNode->_next=NULL;

    if(q->rear==NULL)//front和rear未指向时 赋值newNode给它们当第一个值
    {
        q->front=q->rear=newNode;
    }
    else
    {
        q->rear->_next=newNode;//尾插
        q->rear=q->rear->_next;
    }
    q->size++;//计数
} 

// 队头出队列 
void QueuePop(Queue* q)
{
    assert(q);
    if(q->front->_next==NULL)//只有一个元素时 出列(释放) 置NULL
    {
        free(q->front);
        q->front=q->rear=NULL;
    }
    else//多元素时出列后 front往后移
    {
        QNode* del =q->front;
        q->front=del->_next;
        free(del);
    }
    q->size--;
} 

int QueueEmpty(Queue* q)
{
    assert(q);
    return q->front==NULL &&q->rear==NULL;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->front->_data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
    assert(q);
    //assert(!QueueEmpty(q));

    return q->rear->_data;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
    assert(q);
    return q->size;
} 

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 


// 销毁队列 
void QueueDestroy(Queue* q)
{
    assert(q);
    while(q->size)
    {
        QueuePop(q);//销毁就是一直出列
    }
}
//队列的实现


typedef struct {//队尾无法直接出列 每出一次栈需要出列n-1个到空队列找到最后一个出列的即是栈顶
    Queue q1;
    Queue q2;

} MyStack;
MyStack* myStackCreate() {
    MyStack* newStack=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&newStack->q1);
    QueueInit(&newStack->q2);
    return newStack;
}

void myStackPush(MyStack* obj, int x) {
    assert(obj);
    if(QueueEmpty(&obj->q1)) //哪个不为空尾插哪个
    {
        QueuePush(&obj->q2,x);
    }
    else
    {
        QueuePush(&obj->q1,x);
    }
}

int myStackPop(MyStack* obj) {
    assert(obj);
    Queue* empty =&obj->q1; //判断哪个是空的队列
    Queue* noempty =&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        noempty=&obj->q1;
        empty=&obj->q2;
    }
    while(QueueSize(noempty)>1)//空队列接收另一个队列的出列数据 
    {
        QueuePush(empty, QueueFront(noempty));
        QueuePop(noempty);
    }
    int top=QueueFront(noempty);//队尾出即是出栈
    QueuePop(noempty);
    return top;
}

int myStackTop(MyStack* obj) {
    assert(obj);
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1); //队列的尾就是栈的顶
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

bool myStackEmpty(MyStack* obj) {//判断两个队列是否都为空 都为空则栈为空
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    assert(obj);
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}
